1827D - Two Centroids - CodeForces Solution

/**
 ____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|

**/

#include<bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

void speed()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

const int maxn = 5e5 + 10;
const int maxlog = 21;
int n, p[maxn], timer, tin[maxn], tout[maxn], depth[maxn];
int dp[maxlog][maxn];
vector < int > g[maxn];

void dfs(int v, int p)
{
    tin[v] = ++ timer;
    dp[0][v] = p;
    for (int j = 1; j < maxlog; j ++)
    {
        if (dp[j - 1][v] == -1)
            dp[j][v] = -1;
        else
            dp[j][v] = dp[j - 1][dp[j - 1][v]];
    }
    for (int u : g[v])
    {
        if (u == p)
            continue;
        depth[u] = depth[v] + 1;
        dfs(u, v);
    }
    tout[v] = timer;
}

int fen[maxn];

void add(int v)
{
    for (int i = v; i <= n; i += (i & -i))
        fen[i] ++;
}

int sum(int v)
{
    int s = 0;
    for (int i = v; i > 0; i -= (i & -i))
        s += fen[i];
    return s;
}

int sub_size(int v)

{
    ///cout << "tin " << tin[v] << " " << tout[v] << endl;
    return sum(tout[v]) - sum(tin[v] - 1);
}

void add_vertex(int v)
{

    add(tin[v]);
}

int jump(int v, int x)
{
    for (int j = maxlog - 1; j  >= 0; j --)
    {
        if ((x & (1 << j)) > 0)
            v = dp[j][v];
    }
    return v;
}

void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i ++)
    {
        g[i].clear();
        fen[i] = 0;
    }
    timer = 0;
    for (int i = 2; i <= n; i ++)
    {
        cin >> p[i];
        g[p[i]].push_back(i);
    }

    dfs(1, -1);

    add_vertex(1);
    int centroid = 1, mx = 0;
    for (int i = 2; i <= n; i ++)
    {
        add_vertex(i);
        if (tin[centroid] <= tin[i] && tout[i] <= tout[centroid])
        {
            int v = jump(i, depth[i] - depth[centroid] - 1), sz = sub_size(v);
            ///cout << "node " << v << endl;;
            if (sz >= (i + 1) / 2)
            {
                centroid = v;
                mx = i / 2;
            }
            else
                mx = max(mx, sz);
        }
        else
        {
            int sz = sub_size(centroid);
            if ((i - sz) >= (i + 1) / 2)
            {
                centroid = dp[0][centroid];
                mx = i / 2;
            }
            else
                mx = max(mx, (i - sz));
        }
        cout << i - 2 * mx << " ";
    }
    cout << endl;

}

int main()
{
    speed();
    int t;
    cin >> t;
    while(t --)
        solve();
    return 0;
}